//
// Created by shenbin on 2022/5/2.
// https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
//

#ifndef ALGORITHM_TRAINNING_C03_LC30_H
#define ALGORITHM_TRAINNING_C03_LC30_H

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

/**
 * 1.
 */
class LeetCode30 {
public:
    vector<int> findSubstring(string s, vector<string> &words) {
        int tot = 0;
        for (string word: words) {
            tot += word.length();
            wordsMap[word]++;
        }
        vector<int> ans;
        // 逐个字符扫描，取tot长度为字符
        for (int i = 0; i + tot <= s.length(); i++) {
            if (valid(s.substr(i, tot), words)) {
                ans.push_back(i);
            }
        }
        return ans;
    }

private:
    unordered_map<string, int> wordsMap;

    bool valid(string str, vector<string> &words) {
        int k = words[0].length();
        // 每次取k个字符
        unordered_map<string, int> splitWords;
        for (int i = 0; i < str.length(); i += k) {
            splitWords[str.substr(i, k)]++;
        }
        return equalsMap(wordsMap, splitWords);

    }

    bool equalsMap(unordered_map<string, int> &a, unordered_map<string, int> &b) {
        for (auto &key_and_value: a) {
            string key = key_and_value.first;
            int value = key_and_value.second;
            if (b.find(key) == b.end() || b[key] != value) return false;
        }
        for (auto &key_and_value: b) {
            string key = key_and_value.first;
            int value = key_and_value.second;
            if (a.find(key) == a.end() || a[key] != value) return false;
        }
        return true;
    }
};

#endif //ALGORITHM_TRAINNING_C03_LC30_H
